//给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 
//不重复 的三元组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 3000 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// 
//
// 
// 注意：本题与主站 15 题相同：https://leetcode-cn.com/problems/3sum/ 
//
// Related Topics 数组 双指针 排序 👍 156 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-01-12 22:39:32
 * @description LCR 007.三数之和
 */
public class OneFGaJU{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 OneFGaJU fun=new OneFGaJU();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //排序后，固定最左边，在右边区间内枚举所有可能的组合，同时跳过重复的，包括右区间组合重复和左固定重复
	public List<List<Integer>> threeSum(int[] nums){
		List<List<Integer>> res=new ArrayList<>();

		int length = nums.length;
		if(nums==null||length<3) return res;
		Arrays.sort(nums);

		for (int i = 0; i < length; i++) {
			//如果起始值已经大于0。中间找不到和小于0 的数
			if(nums[i]>0){
				break;
			}
			//去重，重复的元素只找第一个
			if(i>0&&nums[i]==nums[i-1]) continue;
			int l=i+1;
			int r=length-1;
			//找出与i相加等于0的所有lr
			while (l<r){
				int sum=nums[i]+nums[l]+nums[r];
				//等于0保存解
				if(sum==0){
					res.add(Arrays.asList(nums[i],nums[l],nums[r]));
					//去重，移动左右指针
					while (l<r&&nums[l]==nums[l+1]){
						l++;
					}
					while (l<r&&nums[r]==nums[r-1]){
						r--;
					}
					l++;
					r--;

				}else if(sum<0){
					l++;
				}else if(sum>0){
					r--;
				}
			}
		}
		return res;

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
